/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-01-17
 * Time: 20:40
 */
public class TestMyself {





    /**
     * 堆排序
     * @param array
     */
    public static void Heapsort(int[] array) {
        //排升序建大堆
        //排降序建小堆
        creatHeap(array);//这里是建小堆->升序
        //交换
        int end = array.length-1;
        while (end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }


    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static void creatHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }


    private static void shiftDown(int[] array, int parent, int len) {
        int child = 2*parent+1;
        while (child<len) {
            //有左孩子,且最小为左孩子
            if (child+1<len && array[child]>array[child+1]) {
                child++;
            }
            //有右孩子，最小为右孩子
            if (array[parent]>array[child]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;

                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }


}
